1. Field of the Invention
The present invention relates to a method for displaying images in a computer controlled raster display system. More particularly, the present invention relates to an apparatus and method for scan converting shaded polygons and for determining the coverage of pixels in polygons in a computer controlled raster display system.
2. Prior Art
Many computer systems today are capable of displaying complex 3-dimensional curves and solids on display devices which are controlled by these computer systems. These complex 3-dimensional solids and curves are typically displayed interactively to allow the user to manipulate the object. Well known graphics techniques for rendering these 3-dimensional curves and solids, such as Gouraud shading, hidden surface algorithms, clipping, filling polygons and coordinate transformations are used in order to generate the displayed object on a display device, such as a CRT video display which is controlled by the computer system.
These various computer systems often rely on converting a polygon representation of the solid to a raster scanned image which is stored in the frame buffer of the computer system. In this circumstance, it will typically be necessary to convert from the vertices of the polygon which are calculated in the clipping and transformation manipulations to an array of parameter data which is stored in a frame buffer array at the resolution of the display device. In other words, it is necessary to convert from the specification of parameter values (e.g. color in the form of "RGB" or other representations of color and Z values and other useful parameters) at each vertex of a polygon to parameter values at each picture element (pixel) of the output display device. This task becomes difficult and computationally expensive when the polygon to be displayed is shaded such that the interior of the polygon includes parameter values and is not merely an outline of the border of the polygon. In this situation, the scan conversion process must fill all pixels within the polygon with appropriate parameter values from only the parameter values of the vertices of the polygon.
FIG. 1 represents a typical method of the prior art, which is briefly discussed at pages 398-399 of Newman and Sproull, Principles of Interactive Computer Graphics, McGraw Hill, 1979. In this technique, scan conversion and filling begins by receiving the parameter values at the vertices of the polygon, in this case a triangle as shown in FIG. 1. For example, the vertex V0 will have specified with it an X and Y value (X0 and Y0) and parameter values such as RGB and perhaps a Z value and other parameter values. Similarly, vertex V1 and V2 will also have parameter values associated with the locations of the vertices V1 and V2. It will be appreciated that the triangle shown in FIG. 1 is ready for scan conversion as it has been converted to the output device coordinate space at subpixel resolution; thus, for example the scan lines are shown as horizontal lines (rows) and the integer X values are shown as columns. A pixel center is assumed to be at the intersection of each row and column, for example as shown at X=11 and Y=4. It will be appreciated that each column is parallel to an orthogonal axis of the display device.
In the prior art methods for scan converting, parameter values are computed at both edges of a triangular polygon which intersect a particular scan line from the parameter values at the appropriate vertices. For example, for scan line Y=6, parameter values along the edge V0-V2 will be computed at location 12 (which is not a pixel center) and the parameter values for location 15 along edge V1-V2 will also be computed. These values along the edge of the polygon are computed by interpolating between the parameter values along the particular edge. For instance, locations 10, 11, and 12 have their parameter values computed by interpolating the parameter values for V0 and V2 in the well known manner. After interpolating the parameter values at all intersections of each edge of the polygon with all scan lines running through the polygon, then actual parameter values for pixel centers are then interpolated along each scan line by interpolating between the parameter values at the edges along that scan line. Thus for example, the parameter value for the pixel at 8,5 will be calculated by interpolating the parameter values at location 11 and 16 of FIG. 1.
In an alternative embodiment of the prior art method of scan converting filled polygons, parameter values at the intersections of each column with each edge are calculated and these values are used for interpolating parameter values at pixel centers along each column. Thus, parameter values at locations 21 and 22 would be calculated by interpolating from the parameter values at V0 and V2 for location 21 and from the parameter values at V0 and V1 for location 22 and then the parameter value at pixel center X=3, Y=4 would then be calculated by interpolating between the parameter values at locations 21 and 22.
It will be appreciated that considerable computational effort is required in order to first calculate parameter values along the edges of the polygons at each appropriate intersection. These calculations are somewhat wasteful because the values calculated are not themselves ultimately displayed but rather are used to calculate other values which will be ultimately displayed. This increased computational load on the computer system results in slower drawing of images to a display device. The present invention seeks to improve the method of scan converting filled polygons by avoiding the calculation of parameter values which are not themselves used for display.
After a parameter value is computed for a particular pixel center within a polygon, it may be necessary to modify the parameter value in order to make the appearance of the filled polygon on a display device satisfactory to a user. This is particularly true of pixel centers near edges of the polygons where the original parameter value of the pixel center clashes (e.g. very different colors) with a parameter value of a pixel center which is just outside of the filled polygon. This clashing of parameter values often results in the jagged appearance of the edges of a polygon, which makes the appearance of the polygon distorted on a display device of the computer system. This appearance is largely due to the fact that only a portion of the actual pixel is obscured by the polygon and it is also due to the fact that the pixel on the display device has an actual size rather than being an infinitely small dot.
Prior art techniques of determining the coverage of a pixel and of blending or anti-aliasing the pixel within a filled polygon have included numerous techniques which are typically cumbersome and are often inaccurate in determining the portion of the pixel obscured by the polygon (i.e. in determining coverage). It is an object of the present invention to provide an improved technique for determining the portion of the pixel obscured by the polygon to allow for improved blending and anti-aliasing of filled polygons to thereby improve the appearance of images displayed in the computer system of the invention.